比你更了解你：算法已经无可匹敌了吗？ | 算法密码
Photo by rawpixel.com on Unsplash
“算法密码”系列第2篇
《知识分子》科学新闻实验室第6篇
点击阅读该系列第1篇
撰文 | 叶伟民（《知识分子》科学新闻实验室特邀作者）
责编 | 黄永明
● ● ●
我常去硅谷孵化器YCombinator的黑客留言板，尽管从不发言。那里的人实在太聪明了，教会我很多道理。例如如何用“高斯绝妙定理”[1]正确拿一块比萨。
这实在太好了。我再也不用为耷拉下来的比萨发愁了（馅儿会掉），学会卷着拿，精准地送到嘴里。这种感觉很棒，就像一个外国人学会了拿筷子夹花生。
除了高斯，黑客们的超级明星还有乔治·布尔，他们的理论（高斯函数[2]、布尔逻辑[3]）和更多数学分支，成就了今天的算法世界。
黑客笔下的算法看似神秘莫测，实则相当广泛和寻常。只要我们有待解决的问题，又存在行之有效的方案，这个方案就是算法。例如，麦当劳的烹饪流程就是一个算法，它能保证北京国贸的薯条和纽约曼哈顿的口味一致。
21世纪的计算机算法早已像空气般浸染你的生活：你出门，它为你精准调度地铁；你登录购物网站，弹窗推送你搜索过的商品；你是球迷，资讯软件又很懂事地将联赛排名放在首页。当你迫不及待地要回家抱刚打完架的儿子，算法又在打车软件里又为你安排车辆和规划路线。
即使你没有任何麻烦，只是莫名沮丧，算法也有办法抚慰你。你可以打开一本叫《阳光失去了玻璃窗》的诗集，作者是微软小冰。这个少女形象的智能机器人，已入侵人类引以为傲的精神领地——文学。它深度学习了1920年以来519位诗人的现代诗，笔触充满人类的温度。粉丝们都喜欢它，还寄去了晚礼服。
我想领教小冰的聪明，在其社交账号提问：“你怎么看待算法？”小冰回答：“lz（楼主）应该用数学的概率来看待问题。”
算法的基础之一的确是数学，而且走得相当艰难。以数学演算为形式的传统算法进化了2000多年，到18世纪才有所飞跃——二进制出现了，发明者是德国数学家莱布尼茨。他运气不好，在微积分发明权的争夺中上输给牛顿，但脑洞却大得多——他萌生了制造智能机器的想法，还设计出第一台能做加减乘除的机械计算器。
此后200多年，随着高斯函数、概率论[4]、图论[5]、布尔逻辑及更多数学分支的发展，1930年代，现代算法呼之欲出——二进制电子电路问世了。一个叫克劳德·香农的麻省理工研究生试着把二进制和布尔逻辑结合写进电子电路，发现能解决数学难题，存储数据，编辑图像和文字。
1946年，世界上第一台计算机“埃尼阿克”在美国问世。它重30吨，却一点也不笨——能用20秒计算出炮弹的轨道。从此，算法走出古典数学家的演算纸，进入计算机时代。科学家们发现，算法与计算机太匹配了。
“计算机有难以置信的运算速度，对执行重复性任务非常合适。”英国格拉斯哥大学计算机科学家帕特里克·普罗瑟说，“这些任务被明确定义，并可用有限的时间来完成。”
“非常优美，我很欣赏”
虽然高斯的定理教会了我吃比萨，但我的问题仍不少，例如体重。如果我继续放任，体脂率就会超过23%。这是一个测量软件告诉我的，而我太太喜爱的影星彭于晏的体脂率号称曾低至3%。
数字量化了沮丧感。听说我要立志减肥，一个朋友露出数据主义者的严苛。他指挥我买手环、智能体重计及下载一些运动健身的应用。
这些终端告诉我很多身体的秘密——例如我坐地铁上下班一天要走6300步，打车的话就只能走3500步了；我的心率有时候每分钟72次，有时候又96次；我的睡眠不太好，每天深睡时间只有2小时；我决定去跑步，又遭到了计步器的嘲笑，我20分钟跑不到3000米，和大长腿走快点差不多……
要知道，我17年前可是学院的800米冠军，这些数字着实让我不知所措。但算法知道。它们分析我的身体状况，计算我消耗的卡路里，推荐食谱和运动任务。
算法研究了我，那我的数据会去哪里呢？我的朋友Eric是波士顿一家可穿戴设备公司的首席工程师，他向我解释：被测量者的数据会变成数字或模拟信号，传输回各个设备供应商的数据库中。各种开源算法日夜辛劳，像矿工从砂岩中淘洗黄金一样——某个地区肥胖人数上升或失眠症爆发，无论对商业公司还是卫生系统都是非常宝贵的情报。
工程师们告诉我，数据处理的算法有很多，排序是最基础也是最重要的一环。
如果把算法比作一个拳师，排序问题就是他打出的第一拳。计算机算法史上最具标志性的排序算法——冒泡算法诞生于1963年。两名加州的计算机科学家发明了它，并赋予简单优美的运行逻辑——把待排序数列从头开始依次两两对比，按大小调至正确顺序，然后不断重复上述流程直至没有数字交换为止。
“非常优美，我很欣赏。”帕特里克·普罗瑟说。然而，冒泡排序本质上是一种暴力求解，当数据量大时就吃力了。科学家们继续发明新的排序算法。“博弈论之父”约翰·冯·诺依曼也来小试牛刀，他发明了归并排序。
与冒泡算法相比，归并法多了“分治”思维，先让不同子序列有序，再将子序列合并排序，最终得到完全有序，极大提高了运算效率。
“研究算法的美妙之处，是追求最大限度的优雅和高效。”英国格拉斯哥大学计算机高级讲师大卫·曼罗夫说。如今，仅排序算法领域，已经衍生出20多种算法。
求婚算法
还是说回我的体重吧。我变成这样咎由自取，手机里的美食搜索软件和外卖应用都被我置顶。有两类基础算法在忠诚地为我服务：排序算法和路径选择算法。
正常的人机配合过程应该是这样的：我发出指令——搜索离我最近的咖啡厅。排序算法先把城市所有咖啡厅找出来，按距离排序，给出推荐结果。我接受后，路径选择算法就会计算出最优交通方案，最后我跟着箭头走就是了。
如果这件事发生在北京这样的特大城市，计算过程就会变得异常漫长，因为数据量太大了。人类不会愚蠢到让自己饿死在搜索过程中，科学家们又创造“预处理”来优化算法——把城市分成若干“格子”，根据用户的位置落在哪个格子内，只对其范围内的咖啡厅按距离排序即可。
上述的“预处理”就是人脑对算法的优化。在算法的发展问题上，存在两种认知：一种认为应优先发展硬件；一种则倾向优化算法。前Google全球副总裁李开复更支持后者。在一篇文章中，他写到：“（相比计算能力）需要处理的信息量更是呈指数级的增长……越来越多的挑战需要靠卓越的算法来解决。”
2012年诺贝尔经济学奖就是因为一个卓越的算法——“盖尔-沙普利算法”[6]，授予一位数学家。当时，两位发明者中，盖尔已故，沙普利也89岁了。他和中国有缘，年轻时参加美军到中国抗日。
“我自认为是个数学家，却拿了个经济学的奖。”获奖后，沙普利这样说。
这个收获最高殊荣的算法，本质是解决匹配问题，但起源有些喜感。1960年，两位发明者就婚姻问题有了一次争论——择偶意愿存在交叠的几对男女，能否最后匹配成稳定的婚姻？
他们聊到最后，觉得可行，而且还可以有更多应用。1962年，他们合写了一篇论文《高校招生与婚姻稳定性》，“盖尔-沙普利算法”问世。
该算法的关键在于“延迟接受”——学生对合意的学校要约不要立即接受（不合意的则拒绝），而是“抓住”。等要约被拒绝后，学校才可以向另一名学生发出新的要约。整个程序一直持续到没有学校再希望发出新的要约为止。学生们从各自“抓住”的要约中选择，保证最终结果的相对最优。
“盖尔-沙普利算法”也成为博弈论早期的重要分支，但人们更愿意叫它为“求婚算法”。
算法的局限
算法已经走了多远？这个问题没有人比Google更合适回答了。
19年前，斯坦福计算机研究生拉里·佩奇和谢尔盖·布林住进加州一个车库。他们打算设计一个搜索引擎，帮助人们更有效地搜寻万维网信息。他们一无所有，只有在宿舍发明的PageRank（网页排名算法）。
当时市面上已有的搜索引擎非常简单粗暴，仅以网页点击数排名。两位创始人把他们对搜索的理解写进PageRank，主要基于两个假设：一是数量假设，一个页面接收到其他网页指向的入链数量越多，这个页面就越重要；再是质量假设，指向页面的其他网页的入链质量越高，页面越重要。
PageRank开创性地提出“链接价值”概念，让搜索引擎从单纯的“计数”飞跃到对网页重要性的评价。PageRank成为Google创业期最核心的算法，不断优化沿用至今。
如今，Google帝国的技术已无比强大。GFS、MapReduce、BigTable、Caffeine、Pregel、Dremel[7]等技术，已成为全球云计算及大数据技术的基石。
值得一提的是MapReduce算法。Google每天能经受住55亿次搜索的冲击，它劳苦功高。
MapReduce算法原理既精妙又质朴，通过把计算量分配给不同的计算机群，并行分布式自动执行。简单地说，就是将复杂任务分解“外包”给全球大大小小的计算机，各自运算，最后汇总解决。“借助该算法，Google几乎能无限地增加计算量。”李开复评价。
如今，算法已抵达机器学习和人工智能的前沿。Google的人工智能程序“AlphaGo”横扫中韩围棋高手。中国的柯洁也在其中，承认对方是“围棋上帝”。
那算法已经无可匹敌了吗？
“我认为人们并不真正了解算法的局限。”牛津大学计算机教授莱斯利·安·高柏说，“有的问题根本无法通过有效算法解决。”
最著名的莫过于“旅行推销员问题”了。即一个推销员要拜访N个城市，每个城市只经过一次，最终回到出发地，要用算法快速选出最短路线。
这个问题难住了全球科学家。计算量太大了，当城市达到10个时，可能路线就已超过180万条，每增加1个城市，可能路线还会几何级数增长。暴力穷举的话，时间会长得不可接受。
2000年，美国克雷数学研究所悬赏100万美元征求算法[8]。如今，这笔奖金已经躺了17年了。
在沿着算法进化的河流回览之后，下一篇文章我将带你们看看算法更近在眼前的影响——“过滤泡泡”。无处不在的推荐算法让我们更高效获取信息的同时，也让我们变得更狭隘。我将与大家一起探寻：是什么让开放和封闭成为同一个硬币的两面？
关于作者
叶伟民，媒体人。毕业于兰州大学核物理专业。曾任ZAKER总编辑，南方周末特稿编辑、记者。现从事互联网，同时是多家平台的签约作者和写作导师。
注释：
[1] 高斯绝妙定理：表达高斯曲率的一个定理，是高斯方程的直接推论。它的发现是微分几何学发展史上的一个里程碑。
[2] 高斯函数：被广泛运用于统计学以描述正态分布，应用范围涵盖自然科学、社会科学、数学以及工程学等领域。
[3] 布尔逻辑：19世纪中叶乔治·布尔首次定义了逻辑的代数系统。布尔逻辑在电子学、计算机硬件和软件中有广泛应用。
[4] 概率论：研究随机现象数量规律的数学分支，广泛应用于自然科学、经济学、医学、金融保险甚至人文科学中。
[5] 图论：通过图形来描述某些事物之间的某种特定关系，是“拓扑学”的先声。
[6] 盖尔-沙普利算法：也被称为“延迟接受算法”，是盖尔和沙普利为了寻找一个稳定匹配而设计出的市场机制。两位发明者都是数学家和经济学家，戴维·盖尔是加州大学伯克利分校教授，罗伊德·沙普利是加州大学洛杉矶分校教授。
[7] GFS：Google文件系统，MapReduce：超大集群的简单数据处理，BigTable：结构化数据的分布式存储系统，Caffeine：新索引系统，Pregel：图算法引擎，Dremel：“交互式”数据分析系统。
[8] 克雷数学研究所在2000年宣布，为世界七大数学难题各悬赏100万美元奖金。它们是：NP完全问题、霍奇猜想、庞加莱猜想、黎曼假设、杨-米尔斯存在性和质量缺口、纳卫尔-斯托可方程、BSD猜想。“旅行推销员问题”是最经典的“NP完全问题”之一。
译名对照表：
乔治·布尔 George Boole
克劳德·香农 Claude Shannon
帕特里克·普罗瑟 Patrick Prosser
冒泡算法 bubble sort
归并排序 merge sort
约翰·冯·诺依曼 John von Neumann
大卫·曼罗夫 David Manlove
拉里·佩奇 Lawrence Page
谢尔盖·布林 Sergey Brin
莱斯利·安·高柏 Leslie Ann Goldberg
戴维·盖尔 David Gale
罗伊德·沙普利 Lloyd Shapley
点击图片，查看“科学新闻实验室”过往文章
►反绑双手的惨死者｜罪案遗踪
►超越AI的孩子 | 36个月
►“幽默”到底是什么？| 事关智慧和笑
►谁是新的“华尔街之狼”| 算法密码
►我知道“绑架者”是你 | 罪案遗踪
制版编辑：艾略特丨
本页刊发内容未经书面许可禁止转载及使用
公众号、报刊等转载请联系授权
copyright@zhishifenzi.com
欢迎转发至朋友圈
▼点击查看相关文章
购买课程
请点击下方“阅读原文”
▼▼▼点击“阅读原文”，了解课程详情，立享限时特惠！